import TreeTraversal.TreeNode;

import java.util.LinkedList;

public class Leetcode98 {
    long prev = Long.MIN_VALUE;
    //解法1：中序遍历递归实现
    public boolean isValidBST(TreeNode node){
        if(node == null){
            return true;
        }
        boolean a = isValidBST(node.left);
        if(!a){
            return false;
        }
        if(prev >= node.val){
            return false;
        }
        prev = node.val;
        return isValidBST(node.right);
    }
    //解法2：中序遍历非递归实现
    public boolean isValidBST1(TreeNode node){
        TreeNode p = node;
        long prev = Long.MIN_VALUE;
        LinkedList<TreeNode> stack = new LinkedList<>();
        while( p != null || !stack.isEmpty()){
            if(p != null){
                stack.push(p);
                p = p.left;
            }else{
                TreeNode pop = stack.pop();
                if(prev >= pop.val){
                    return false;
                }
                prev = pop.val;
                p = pop.right;
            }
        }
        return true;
    }
    //解法3：上下限递归实现
    public boolean isValidBST2(TreeNode node){
        return doValidBST2(node,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    private boolean doValidBST2(TreeNode node, long min, long max){
        if(node == null){
            return true;
        }
        if(node.val <= min || node.val >= max){
            return false;
        }
        return doValidBST2(node.left,min,node.val) && doValidBST2(node.right,node.val,max);
    }
}
